package history

type TreeNode2 struct {
	Val   int
	Left  *TreeNode2
	Right *TreeNode2
}

/**
 * @Description: 236. 二叉树的最近公共祖先 中等
 * @Keyword:递归寻找
 * @Author: kami
 * @Date: 2022/6/16 14:56
 **/
func lowestCommonAncestor(root, p, q *TreeNode2) *TreeNode2 {
	// LCA 问题
	if root == nil || root == p || root == q {
		return root
	}
	// 左右子树是否包含目标节点
	var left = lowestCommonAncestor(root.Left, p, q)
	var right = lowestCommonAncestor(root.Right, p, q)

	// 如果 当前节点左子树包含一个，右子树包含一个，则当前节点就是最近祖先
	if left != nil && right != nil {
		return root
	}
	if left != nil {
		return left
	}
	if right != nil {
		return right
	}

	return nil
}
